﻿SmitearWebGL.Utils.QuickSort = function( array, members, pred )
{
	var h = 1;

	//find the largest h value possible
	while ((h * 3 + 1) < members)
	{
		h = 3 * h + 1;
	}

	//while h remains larger than 0
	while( h > 0 )
	{
		// for each set of elements (there are h sets)
		for (var i = h - 1; i < members; i++)
		{
			//pick the last element in the set
			var B = array[i];
			var j = i;

			//compare the element at B to the one before it in the set
			//if they are out of order continue this loop, moving
			//elements "back" to make room for B to be inserted.
			for( j = i;
			(j >= h) && pred(B,array[j-h]);
			j -= h)
			{
				array[j] = array[j-h];
			}

			//  insert B into the correct place
			array[j] = B;
		}

		//all sets h-sorted, now decrease set size
		h = h / 3;
	}
}